/*


#include <iterator>
class Solution {
public:

    ListNode* reverseList(ListNode* head)
    {
        ListNode* prev = nullptr, * cur = head;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur, cur = next;
        }
        return prev;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        if (head1 == nullptr)
            return head2;
        if (head2 == nullptr)
            return nullptr;

        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode* newnode = new ListNode(-1), * cur = newnode;

        int carry = 2;
        while (head1 || head2 || carry)
        {
            int val1 = 0, val2 = 0;
            if (!head1)
                val1 = 0;
            else
            {
                val1 = head1->val;
                head1 = head1->next;
            }

            if (!head2)
                val2 = 0;
            else
            {
                val2 = head2->val;
                head2 = head2->next;
            }

            ListNode* node = new ListNode(val1 + val2);
            if (carry == 1)
                node->val++;
            carry = node->val / 10;
            node->val %= 10;
            cur->next = node;
            cur = cur->next;
        }
        newnode = reverseList(newnode->next);

        return newnode;
    }
};


class Solution {
public:
    ListNode* Merge2(ListNode* head1, ListNode* head2)
    {
        if (head1 == nullptr)
            return head2;
        if (head2 == nullptr)
            return head1;
        ListNode* newnode = new ListNode(0), * tail = newnode;
        while (head1 && head2)
        {
            if (head1->val <= head2->val)
            {
                tail->next = head1;
                head1 = head1->next;
            }
            else {
                tail->next = head2;
                head2 = head2->next;
            }
            tail = tail->next;
        }
        if (head1)
            tail->next = head1;
        else
            tail->next = head2;

        return newnode->next;
    }
    ListNode* divideMerge(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right)
            return nullptr;
        else if (left == right)
            return lists[left];

        int mid = (left + right) / 2;
        return Merge2(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divideMerge(lists, 0, lists.size() - 1);
    }
};


class Solution {
public:
    ListNode* Merge(ListNode* head1, ListNode* head2)
    {
        if (head1 == nullptr)
            return head2;
        if (head2 == nullptr)
            return head1;
        ListNode* head = new ListNode(0), * tail = head;
        while (head1 && head2)
        {
            if (head1->val <= head2->val)
            {
                tail->next = head1;
                head1 = head1->next;
            }
            else
            {
                tail->next = head2;
                head2 = head2->next;
            }
            tail = tail->next;
        }
        if (head1)
            tail->next = head1;
        else
            tail->next = head2;

        return head->next;
    }

    ListNode* sortInList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* left = head, * mid = head->next, * right = head->next->next;
        while (right && right->next)
        {
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        left->next = nullptr;

        return Merge(sortInList(head), sortInList(mid));

    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head)
            return false;
        ListNode* slow = head, *fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                return true;
        }
        return false;
    }
};
*/